package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 错误写法
 * step = 1
 * A 4
 * B 3
 * C 2
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC621_1 implements Greedy {
    public int leastInterval(char[] tasks, int n) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int c : tasks) {
            counts.compute(c, (key, oldValue) -> oldValue == null ? 1 : oldValue + 1);
        }
        List<Integer> cnts = counts.values().stream()
                .sorted().collect(Collectors.toList());

        TreeMap<Integer, Integer> groups = new TreeMap<>(Comparator.reverseOrder());//key是group长度, v是个数
        int last = 0;
        for (int i = 0; i < cnts.size(); i++) {
            if (cnts.get(i) - last > 0)
                groups.put(cnts.size() - i, cnts.get(i) - last);
            last = cnts.get(i);
        }
        System.out.println(groups);
        int totalTime = 0;
        for (Map.Entry<Integer, Integer> groupEntry : groups.entrySet()) {
            totalTime += Math.max(groupEntry.getKey(), n + 1) * groupEntry.getValue();
        }
        if (groups.lastEntry().getKey() < n + 1) {
            totalTime = totalTime - (n + 1) + groups.lastEntry().getKey();
        }
        return totalTime;
    }

    public static void main(String[] args) {
        System.out.println(new LC621_1().leastInterval(new char[]{
                'A', 'A', 'A', 'B', 'B', 'B'}, 2));//8
        System.out.println(new LC621_1().leastInterval(new char[]{
                'A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E'}, 4));//10
        System.out.println(new LC621_1().leastInterval(new char[]{
                'A', 'A', 'A', 'B', 'B', 'B'}, 2));//8
        System.out.println(new LC621_1().leastInterval(new char[]{
                'A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'E'}, 2));//12


        System.out.println(new LC621_1().leastInterval(new char[]{
                'A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'}, 2));//20
        //FIXME 我要吐了, 这个致命的testcase
        // 这种贪心也不对???????

        //FIXME 又来一种思路??? 尽量让idle的地方最少没错, 但是也不能浪费.
        // 6 1 1 1 1 |2
        // 3 3 3 2 1 |2
        // 3 3 |2
        // 应该结合这两个代码中的思想, 形成第三版:
        // 3 3 3 2 1
        // ABC ABC ABC DE_D 错误解, 其实一组一组考虑,前两组是ok的
        // 到ABC DE_D这里, D是频次最高的, 应该先安排D了
    }
}
